package com.alu.search;

/**
 * 二分法查找
 * 
 * @author Administrator
 *
 */
public class BinarySearch {
	public int rank(int key, int sorted[]) {
		
		// 低位和高位
		int low = 0;
		int high = sorted.length-1;
		
		// 低位不等于高位，继续找
		while(low != high) {
			int mid = low + (high-low)/2;
			
			// 要找的值在中间值之前，把高位移动到中间值前一位
			if(sorted[mid] > key) {
				high = mid-1;
			} else if(sorted[mid] < key) {
				// 要找的值在中间值之后，把高位移动到中间值后一位
				low = mid+1;
			} else {
				return mid;
			}
		}
		
		return -1;
	}
}
